package com.mdnote.structure.treebaswe;

import org.omg.CORBA.PRIVATE_MEMBER;

import java.util.Stack;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/8/30
 * @description 线索化二叉树
 * @RefenceL ：https://www.cnblogs.com/lishanlei/p/10707830.html
 */
public class ThreadedInfixBinaryTree {
    /**
     * 节点
     */
    private static class Node {
        private int value;
        private Node left;
        private Node right;

        /**
         * 父节点，后序线索化要用
         */
        private Node parent;

        /**
         * 左子节点的类型 0 普通节点  1 前驱节点
         */
        private int leftType;
        /**
         * 右子节点的类型 0 普通节点 1 后继节点
         */
        private int rightType;
        /**
         * 上一个节点，必须是static
         */
        private static Node pre;

        public Node(int value) {
            this.value = value;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public void setRight(Node right) {
            this.right = right;
        }

        /**
         * 谦虚遍历
         */
        private void preOrder() {
            System.out.print(this.value + " ");
            if (this.left != null) {
                this.left.preOrder();
            }
            if (this.right != null) {
                this.right.preOrder();
            }
        }

        /**
         * 终须遍历
         */
        private void infixOrder() {
            if (this.left != null) {
                this.left.infixOrder();
            }
            System.out.print(this.value + " ");
            if (this.right != null) {
                this.right.infixOrder();
            }
        }

        /**
         * 后续遍历
         */
        private void postOrder() {
            if (this.left != null) {
                this.left.postOrder();
            }
            if (this.right != null) {
                this.right.postOrder();
            }
            System.out.print(this.value + " ");
        }

        /**
         * 线索化（前序）
         */
        private void threadedPre() {
            // 先处理当前节点
            if (this.left == null) {
                // 让左子节点指向上一个
                this.left = pre;
                this.leftType = 1;
            }
            if (pre != null && pre.right == null) {
                pre.right = this;
                pre.rightType = 1;
            }
            pre = this;
            // 左子节点
            if (this.left != null) {
                this.left.threadedPre();
            }
            // 右子节点
            if (this.right != null) {
                this.right.threadedPre();
            }
        }

        /**
         * 线索化（中序）
         */
        private void threadedInfix() {
            // 先处理左子节点
            if (this.left != null) {
                this.left.threadedInfix();
            }
            // 处理当前节点
            // 处理当前节点的左指针
            if (this.left == null) {
                // 左边指针指向前驱节点
                this.left = pre;
                // 前驱节点的标识
                this.leftType = 1;
            }
            // 处理当前节点的右指针，这一步要在下一次递归时处理
            // this.pre.right 如果有值，就不要线索化了
            if (pre != null && pre.right == null) {
                pre.right = this;
                pre.rightType = 1;
            }
            // 让pre往前走
            pre = this;

            // 处理右子节点
            if (this.right != null) {
                this.right.threadedInfix();
            }
        }

        private void threadedPost() {
            // 左子节点
            if (this.left != null) {
                this.left.parent = this;
                this.left.threadedPost();
            }
            // 右子节点
            if (this.right != null) {
                this.right.parent = this;
                this.right.threadedPost();
            }
            // 处理当前节点
            if (this.left == null) {
                this.left = pre;
                this.leftType = 1;
            }
            if (pre != null && pre.right == null) {
                pre.right = this;
                pre.rightType = 1;
            }
            pre = this;
        }
    }

    public Node root;

    public ThreadedInfixBinaryTree(Node root) {
        this.root = root;
    }

    private void preOrder() {
        root.preOrder();
    }

    private void infixOrder() {
        root.infixOrder();
    }

    private void postOrder() {
        root.postOrder();
    }


    private void threadedPre() {
        this.root.threadedPre();
    }

    private void threadedInfix() {
        this.root.threadedInfix();
    }

    private void threadPost() {
        this.root.threadedPost();
    }

    private void threadedInfixList() {
        Node temp = this.root;
        while (temp != null) {
            // 找到第一个leftType = 1的元素
            while (temp.left != null && temp.leftType != 1) {
                temp = temp.left;
            }
            // 从第一个元素
            System.out.println(temp.value + "");
            while (temp.right != null && temp.rightType == 1) {
                temp = temp.right;
                System.out.println(temp.value + " ");
            }
            // 走到这里说明卡住了，当前的node的rightType为0，所以我们只能跳过他
            temp = temp.right;
        }
    }

    private void threadInfixList() {
        Node temp = this.root;
        while (temp != null) {
            // 输出当前节点
            System.out.println(temp.value + " ");
            // 处理左边节点，直接到叶子节点
            while (temp.left != null && temp.leftType == 0) {
                temp = temp.left;
                System.out.println(temp.value + " ");
            }
            // 剩下的顺着right找就可以了
            while (temp.right != null && temp.rightType == 1) {
                temp = temp.right;
                System.out.println(temp.value + " ");
            }
            // 走到这里说明卡住了，当前的node的rightType为0，所以我们只能跳过他
            temp = temp.right;
        }
    }

    private void threadedPostList() {
        Node preNode = null;
        Node node = root;
        while (node.left != null && node.leftType == 0) {
            node = node.left;
        }
        while (node != null) {
            if (node.rightType == 1) {
                // 是线索
                System.out.println(node.value + " ");
                // 保存一下
                preNode = node;
                node = node.right;
            } else {
                // 不是线索，看看是不是卡在某个节点上了
                if (node.right == preNode) {
                    System.out.println(node.value + " ");
                    if (node == root) {
                        return;
                    }
                    preNode = node;
                    node = node.parent;
                } else {
                    // 为了解决成环而进入的分支
                    node = node.right;
                    while (node != null && node.leftType == 0) {
                        node = node.left;
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Node node1 = new Node(11);
        Node node2 = new Node(22);
        Node node3 = new Node(33);
        Node node4 = new Node(44);
        Node node5 = new Node(55);

        node1.setLeft(node2);
        node1.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);

        ThreadedInfixBinaryTree threadedInfixBinaryTree = new ThreadedInfixBinaryTree(node1);

        threadedInfixBinaryTree.threadPost();
        // 理论上node5的left应该是指向node2 right应该是node1
        System.out.println("线索化后，Node5的left指向" + node5.left.value + "，right指向" + node5.right.value);
        threadedInfixBinaryTree.threadedPostList();

    }
}
